#include <queue>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//奇偶树
class Solution {
public:

    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode*> que;
        int level = 0;
        que.push(root);
        while (!que.empty())
        {
            int size = que.size();

            int prev = level % 2 == 0 ? INT_MIN : INT_MAX;

            for (int i = 0; i<size; ++i)
            {
                TreeNode* cur = que.front();
                int val = cur->val;
                que.pop();

                //判断当前是否于层数寄偶相同
                if (level % 2 == val % 2)
                {
                    return false;
                }

                // 判断递增/递减
                if ( (level%2==1 && prev<=val) || (level%2==0 && prev>=val))
                {
                    return false;
                }
                prev = val;

                if (cur->left != nullptr)
                {
                    que.push(cur->left);
                }
                if (cur->right != nullptr)
                {
                    que.push(cur->right);
                }
            }
            ++level;
        }
        return true;
    }
};